package pers.qianyu.month_202012.date_20201215;

/**
 * [同 date_20201206]
 * 474. 一和零
 * https://leetcode-cn.com/problems/ones-and-zeroes/
 *
 * @author mizzle rain
 * @date 2020-12-15 15:59
 */
public class FindMaxForm {
    // 背包问题，但是这次一个物品有两个属性（二维背包问题）
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] count = new int[len][2];
        for (int i = 0; i < len; i++) {
            count[i] = count01(strs[i]);
        }
        int[][] dp = new int[m + 1][n + 1];
        for (int[] arr : count) {
            for (int a = m; a >= 0; a--) {
                for (int b = n; b >= 0; b--) {
                    if (a - arr[0] >= 0 && b - arr[1] >= 0) {
                        dp[a][b] = Math.max(dp[a][b], dp[a - arr[0]][b - arr[1]] + 1);
                    }
                }
            }
        }
        return dp[m][n];
    }

    private int[] count01(String s) {
        int[] res = new int[2];
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '0') {
                res[0]++;
            } else if (ch == '1') {
                res[1]++;
            }
        }
        return res;
    }
}
